package com.youth.day01;

/**
 * 希尔排序
 * @author Jinx
 * @date 2021/6/13 0:06
 */
public class HillSort {


    /**
     *  时间复杂度：网上说n的1.5次方   比直接插入快
     *  理解：
     *  第一层一半一半遍历：log2 (n/2)    log2的2分子n次方（因为当长度为n时只遍历了n/2次）
     *  第二层遍历的第一层的结果 所以 和第一层一样：log2 (n/2)
     *  第三层在第二层基础上一半一半减：log2 (n/4)
     *  第四层和第三层一样：log2 (n/4)
     */
    public static int[] sort(int[] arr){
        if(arr == null || arr.length < 1){
            return arr;
        }

        //待插入的元素
        int temp;
        // 步长轮数
        for (int step = arr.length/2; step > 0 ; step /= 2) {
            // 待遍历的分组
            for (int i = 0; i < step; i++) {
                // 该组元素进行插入排序
                for (int j = i+step; j < arr.length; j += step) {
                    if(arr[j] < arr[j-step]){
                        temp = arr[j];
                        arr[j] = arr[j-step];
                        for (int k = j-step; k >= 0; k -= step) {
                            if(k-step >= 0){
                                if(temp >= arr[k-step]){
                                    arr[k] = temp;
                                    break;
                                }
                                arr[k] = arr[k-step];
                            }else {
                                arr[k] = temp;
                            }
                        }
                    }
                }
            }
        }

        return arr;
    }
}
